/******************************************************************************************
 * Data Structures in C++
 * ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
 * Junhui DENG, deng@tsinghua.edu.cn
 * Computer Science & Technology, Tsinghua University
 * Copyright (c) 2003-2019. All rights reserved.
 ******************************************************************************************/

#pragma once

/******************************************************************************************
 * 沿关键码k对应的查找链，找到与之匹配的桶（供查找和删除词条时调用）
 * 试探策略多种多样，可灵活选取；这里仅以线性试探策略为例
 ******************************************************************************************/
template <typename K, typename V> int Hashtable<K, V>::probe4Hit ( const K& k ) {
   int r = hashCode ( k ) % M; //从起始桶（按除余法确定）出发
   //*DSA*/printf(" ->%d", r);
   while ( ( ht[r] && ( k != ht[r]->key ) ) || ( !ht[r] && lazilyRemoved ( r ) ) )
      r = ( r + 1 ) % M; //沿查找链线性试探：跳过所有冲突的桶，以及带懒惰删除标记的桶
   //*DSA*/printf(" ->%d", r);
   //*DSA*/printf("\n");
   return r; //调用者根据ht[r]是否为空，即可判断查找是否成功
}
